// 交换字符串中的元素

package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1202 {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        // 把字符串的每个字符看作点，索引对看作边
        UnionFind uf = new UnionFind(s.length());
        for (List<Integer> pair : pairs) {
            // 索引对连接两个点
            uf.union(pair.get(0), pair.get(1));
        }

        // 构造一个map用于存储同一个parent的字符集合
        Map<Integer, List<Character>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            // 找字符i的父亲
            int parent = uf.find(i);
            // 如果没有则创建
            if (!map.containsKey(parent)) {
                map.put(parent, new ArrayList<Character>());
            }
            map.get(parent).add(s.charAt(i));
        }

        // 对每个集合进行排序
        for (Map.Entry<Integer, List<Character>> entry : map.entrySet()) {
            Collections.sort(entry.getValue(), new Comparator<Character>() {
                public int compare(Character c1, Character c2) {
                    return c2 - c1;
                }
            });
        }

        // 拼接字符串
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            // 找到父节点的对应集合，获取并删除最后一个点
            List<Character> l = map.get(uf.find(i));
            sb.append(l.remove(l.size() - 1));
        }
        return sb.toString();
    }

    class UnionFind {
        public int[] parent;
        public int[] rank;

        public UnionFind(int length) {
            parent = new int[length];
            for (int i = 0; i < length; i++) {
                parent[i] = i;
            }
            rank = new int[length];
            Arrays.fill(rank, 1);
        }

        public int find(int idx) {
            return parent[idx] == idx ? parent[idx] : find(parent[idx]);
        }

        public void union(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            if (pa != pb) {
                if (rank[pa] < rank[pb]) {
                    parent[pa] = pb;
                } else if (rank[pa] > rank[pb]) {
                    parent[pb] = pa;
                } else {
                    parent[pa] = pb;
                    // 不能写praent[a] = find(b)，因为不能保证a=find(a)
                    rank[pb]++;
                }
            }
        }
    }
}
